/***************************************************************
*
* DS_CONST_LIST.H
*
* Const-list control
***************************************************************/

#ifndef _DS_CONST_LIST_H_
#define _DS_CONST_LIST_H_

//#include "ap\ap_comm.h"
//#include "ap\ap_dlstat.h"
#include "ds\ds_comm.h"

#pragma once

template <class T, int size> class dsCONST_ARRAY {
   int   nEntry;
   T     list[size];

public:
   dsCONST_ARRAY(int nEntry = 0) : nEntry(nEntry) { /*apMemoryDebugAdd(list, size, AP_MEM_BT_STATIC);*/ }
   ~dsCONST_ARRAY (void) { /*apMemoryDebugRemove(list);*/ }

   int         Length      (void)    const { return nEntry;   }
   int         GetN        (void)    const { return Length(); }
   BOOL        IsEmpty     (void)    const { return nEntry <= 0; }
   int         Capacity    (void)    const { return size;     }
   int         GetDataSize (void)    const { return size * sizeof(T); }
   BOOL        IsValidIdx  (int idx) const { return (idx >= 0 && idx < size && idx < nEntry); }

   // addressing
   const T&    operator [] (int idx) const;
   T&          operator [] (int idx);

   const T&    Front       (void)    const { STRONG_ASSERT(nEntry > 0); return list[0]; }
   T&          Front       (void)          { STRONG_ASSERT(nEntry > 0); return list[0]; }
   const T&    Back        (void)    const { STRONG_ASSERT(nEntry > 0 && nEntry <= size); return list[nEntry - 1]; }
   T&          Back        (void)          { STRONG_ASSERT(nEntry > 0 && nEntry <= size); return list[nEntry - 1]; }

   T *         Begin       (void)          { return list; }
   const T *   Begin       (void) const    { return list; }

   // adding
   T&          PushFront   (const T &val = T()); // takes O(n)
   T&          PushBack    (const T &val = T()); // takes O(1)
   void        Add         (const T &val);
   void        Insert      (int pos, const T *begin, int num);
   void        Insert      (int pos, const T &val) { Insert(pos, &val, 1); }
   void        Fill        (int n, const T &val); 

   // fast version without copyctor calls
   void        ResizeUninitialized(int newSize);
   
   enum INS_SORT{INS_DUP_REPLACE, INS_DUP_IGNORE, INS_DUP_ERROR, INS_DUP_RIGHT};

   template <class CMP>
   int         InsertSorted(const T &val, const CMP &cmp, INS_SORT dup = INS_DUP_IGNORE);

   // removing, takes O(n)
   void        Remove      (int idx);
   void        Clear       (const T &val = T()); 
   // removing, takes O(1)
   T           PopBack     (const T &val = T());

   // fast resizing
   void        AdvanceBack (int n = 1);
   void        SetN        (int n);

   // sorting, uses qsort
   void        Sort        (int (__CDECL cmp) (const void*, const void*));

   // finding
   int         Find        (const T &val) const;

   template <class KEY>
   int         FindSorted  (const KEY & key) const { return FindSorted(key, dsCMP()); }

   template <class CMP, class KEY>
   int         FindSorted  (const KEY &key, const CMP &cmp, int* insertPos = NULL) const;

   template <typename CMP> int Find (const T &val, CMP &cmp) const
   {
      int i;
      for (i = 0; i < Length(); i++) {
         if (cmp(list[i], val) == 0) {
            return i;
         }
      }
      return -1;
   }

   template <typename CMP> int Find (void *data, CMP &cmp) const
   {
      int i;
      for (i = 0; i < Length(); i++) {
         if (cmp(list[i], data) == 0) {
            return i;
         }
      }
      return -1;
   }

#ifdef _FILEIO_H_
   // save/load
   void     Read                (class fioFILE *stream);
   void     Write               (class fioFILE *stream);
#endif // _FILEIO_H_
};

namespace ds {
   template <class T, int Size>
   class ARRAY {
   public:
      T &            operator [] (int index)         { STRONG_ASSERT(index >= 0 && index < Size); return list[index]; }
      const T &      operator [] (int index) const   { STRONG_ASSERT(index >= 0 && index < Size); return list[index]; }

      T *            Begin(void)                     { return list; }
      const T *      Begin(void) const               { return list; }
      int            Length(void) const              { return Size; }
      int            SizeOf(void) const              { return Size * sizeof(T); }

      ARRAY          (void) {
         //for (int i = 0; i < Size; ++i) {
         //   list[i] = T();
         //}
      }

      explicit ARRAY          (const T & val) {
         for (int i = 0; i < Size; ++i) {
            list[i] = val;
         }
      }

      ARRAY          (const ARRAY & p) {
         for (int i = 0; i < Size; ++i) {
            list[i] = p.list[i];
         }
      }

      void           operator = (const ARRAY & p) {
         for (int i = 0; i < Size; ++i) {
            list[i] = p.list[i];
         }
      }

   private:
      T list[Size];
   };
}

/***************************************************************
* dsCONST_ARRAY::operator[] ()
***************************************************************/
template <class T, int size> __INLINE const T& dsCONST_ARRAY<T, size>::operator [](int idx) const
{
   STRONG_ASSERT(IsValidIdx(idx));
   return list[idx];
}

/***************************************************************
* dsCONST_ARRAY::operator [] ()
***************************************************************/
template <class T, int size> __INLINE T& dsCONST_ARRAY<T, size>::operator [](int idx)
{
   STRONG_ASSERT(IsValidIdx(idx));
   return list[idx];
}

/***************************************************************
* dsCONST_ARRAY::Add ()
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::Add (const T &val)
{
   STRONG_ASSERT(Length() < size);

   nEntry++;
   list[nEntry - 1] = val;
}

/***************************************************************
* dsCONST_ARRAY::ResizeUninitialized ()
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::ResizeUninitialized(int newSize)
{
   STRONG_ASSERT(newSize <= size);
   
   nEntry = newSize;
}

/***************************************************************
* dsCONST_ARRAY::Insert()
*
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::Insert(int pos, const T *begin, int num)
{
   STRONG_ASSERT(nEntry + num <= size);
   if (num == 0) {
      return;
   }

   memmove(&list[pos + num], &list[pos], (nEntry - pos) * sizeof(T));

   for (int i = 0; i < num; i++) {
      New(&list[pos + i], *begin);
      begin++;
   }

   nEntry += num;
   return;
}


/***************************************************************
* dsCONST_ARRAY::InsertSorted()
*
***************************************************************/
template <class T, int size> 
template <class CMP> __INLINE int dsCONST_ARRAY<T, size>::InsertSorted(const T &val, const CMP &cmp, INS_SORT dup)
{
   int ins_pos;
   int found = FindSorted(val, cmp, &ins_pos);

   if(found == -1) {
      STRONG_ASSERT(ins_pos >= 0 && ins_pos < size);
      Insert(ins_pos, val);
   } else {
      switch (dup) {
         case INS_DUP_REPLACE: list[ins_pos] = val; break;
         case INS_DUP_RIGHT:   Insert(ins_pos, val); break;
         case INS_DUP_IGNORE:  break;
      }
   }
   return ins_pos;
}


/***************************************************************
* dsCONST_ARRAY::PushBack()/PushFront()
*
***************************************************************/
template <class T, int size> __INLINE T& dsCONST_ARRAY<T, size>::PushBack (const T &val)
{
   Add(val);

   return Back();
}

/**************************************************************************
* T, int size> __INLINE T& dsCONST_ARRAY<T, size>::PushFront()            *
*                                                                         *
**************************************************************************/
template <class T, int size> __INLINE T& dsCONST_ARRAY<T, size>::PushFront (const T &val)
{
   if (Length() >= size) {
      ASSERT_ALOOF_CODE();
   } else {
      list[nEntry].~T(); // destroy last element, that will be overwritten

      // if array is not empty, copying is needed
      if (Length() != 0) {
         memmove(list + 1, list, Length() * sizeof(T));
      }

      nEntry++;
      New(&Front(), val);// construct there new element     
   }
   
   return Front();
}

/***************************************************************
* dsCONST_ARRAY::Remove()
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::Remove (int idx)
{
   if (!IsValidIdx(idx)) {
      ASSERT_ALOOF_CODE();
      return;
   }
     
   // if we are removing last element then no copying is needed
   if (idx != Length() - 1) {
      list[idx].~T(); // destroy element, that will be overwritten
      memmove(list + idx, list + idx + 1, (Length() - idx - 1) * sizeof(T));
      New(&Back());   // last element was copied, construct there new element
   }
   
   nEntry--;

   return;
}

/***************************************************************
* dsCONST_ARRAY>::AdvanceBack ()
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::AdvanceBack (int n)
{
   if (Length() + n > size || Length() + n < 0) {
      ASSERT(FALSE);
      return;
   }

   nEntry += n; 
   return;
}

/***************************************************************
* dsCONST_ARRAY>::SetN ()
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::SetN (int n)
{
   STRONG_ASSERT(n <= size && n >= 0);
   nEntry = n;
}

/***************************************************************
* dsCONST_ARRAY::Clear()
*
* It ensures that all entries in the array are reset to default values
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::Clear (const T &val)
{
   for (int i = 0; i < Length(); i++) {
      list[i].~T();
      New(&list[i], val);
   }

   nEntry = 0;
   return;
}

/***************************************************************
* dsCONST_ARRAY::Fill()
*
* Fill first "n" elements with value "val"
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::Fill(int n, const T &val)
{
   STRONG_ASSERT(n <= size && n >= 0);

   // Clear existing elements
   for (int i = 0; i < Length(); i++) {
      list[i].~T();
   }

   SetN(n);

   for (int i = 0; i < Length(); i++) {
      New(&list[i], val);
   }

   return;
}

/***************************************************************
* dsCONST_ARRAY::PopBack()
*
***************************************************************/
template <class T, int size> __INLINE T dsCONST_ARRAY<T, size>::PopBack(const T &val)
{
   T ret = Back();
   Back().~T();
   New(&Back(), val);
   nEntry--;
   return ret;
}


/***************************************************************
* dsCONST_ARRAY::Find()
***************************************************************/
template <class T, int size> __INLINE int dsCONST_ARRAY<T, size>::Find (const T &val) const
{
   for (int i = 0; i < Length(); i++) {
      if (list[i] == val) {
         return i;
      }
   }

   return -1;
}

/***************************************************************
* dsCONST_ARRAY::Sort()
***************************************************************/
template <class T, int size> __INLINE void dsCONST_ARRAY<T, size>::Sort (int (__CDECL cmp)(const void*, const void*))
{
   qsort(list, Length(), sizeof(T), cmp);
}


/***************************************************************
* dsCONST_ARRAY::FindSorted()
***************************************************************/
template <class T, int size>  
template <class CMP, class KEY> __INLINE int dsCONST_ARRAY<T, size>::FindSorted(const KEY &key, const CMP &cmp, int* bestPos) const
{
   int begin = 0; 
   int end = nEntry;

   for(;;) {
      if (begin == end) {
         if(bestPos) *bestPos = end;
         break;
      }

      int pos = (begin + end) >> 1;

      int rc = cmp.cmp(list[pos], key);
      if (rc > 0) { 
         end = pos; // key is less -> look left half
      } else if (rc < 0) { 
         begin = pos + 1; // key is greater -> look right half
      } else {
         if(bestPos) *bestPos = pos;
         return pos; // key found
      }
   }
   return -1;
}


#ifdef _FILEIO_H_
/*************************************************************
* Read()/Write()
*************************************************************/
template <class T, int size> void dsCONST_ARRAY<T, size>::Write (fioFILE *stream)
{
   stream->Write(Length());
   if (Length() > 0) {
      stream->Write((BYTE*)list, sizeof(T)*Length());
   }
   return ;
}
template <class T, int size> void dsCONST_ARRAY<T, size>::Read(fioFILE *stream)
{
   int s;
   stream->Read(&s);
   SetN(s);
   if (s > 0) {
      stream->Read((BYTE*)list, sizeof(T)*s);
   }
   return ;
}
#endif // _FILEIO_H_

#endif // _DS_CONST_LIST_H_

//
// End-of-file DS_CONST_LIST.H
//
